package lu.uni.adtool.adtconverter;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.EnumMap;

import lu.uni.adtool.adtconverter.enums.NodeType;
import lu.uni.adtool.adtconverter.enums.PathType;
import lu.uni.adtool.adtconverter.enums.StratType;

/**
 * Computes the tree edit distance using RTED algorithm.
 *
 * @author Piotr Kordy based on code by Mateusz Pawlik.
 */
public class RTED_InfoTree{
  /**
   * Stores the number of relevant subproblems.
   */
  //public long counter;
  /**
   * Statistics for strategies LEFT,RIGHT,HEAVY,SUM.
   */
  //public int[] strStat = new int[5];
  // trees
  private InfoTree it1;
  private InfoTree it2;
  private LabelDictionary ld;
  // arrays
  /**
   * Strategy array.
   */
  private StratType[][] strategyArray;
  /** an array for storing the distances between every pair of subtrees
   */
  private EditPath[][] delta;
  /**
   * stores the distances difference of a form delta(F,G)-delta(F°,G°) for every
   * pair of subtrees, which is at most 1.
   */
  private int[][] deltaBit;
  /**
   *  Stores a forest preorder for given i and j.
   */
  private int[][] IJ;
  private EnumMap<NodeType,long[][]> costV;
  //private long[][][] costV;
  //private long[][] costW;
  private EnumMap<NodeType,long[]> costW;

  private EditPath da;
  private EditPath db;
  private EditPath dc;
  //private StratType previousStrategy;
  /**
   * deletion operations costs.
   */
  private int costDel;
  /**
   * insertion operations costs.
   */
  //private int costIns;
  /**
   * renaming operations costs.
   */
  private int costPartialMatch;
  private int costFullMatch;

  /**
   * Constructs a new instance.
   * @param newCostDel cost of deleting or adding node
   * @param newCostMatch cost of matching when only label needs to be changed
   * @param newFullMacth cost of matching when type needs to be changed
   */
  public RTED_InfoTree(int newCostDel, int newCostMatch, int newFullMacth)
  {
    costDel = newCostDel;
    costPartialMatch = newCostMatch;
    costFullMatch = newFullMacth;
    //counter = 0;
  }
  /**
   * Computes the tree edit distance between trees t1 and t2.
   * 
   * @param t1 left tree to compare.
   * @param t2 right tree to compare.
   * @return tree edit sequence of actions to restore tree t1 from t2
   */
  public final EditPath nonNormalizedTreeDist(final LblTree t1, final LblTree t2)
  {
    init(t1, t2);
    //System.out.println("L:"+t1.toString(2));
    //System.out.println("R:"+t2.toString(2));
    computeOptimalStrategy();
    EditPath result =  computeDistUsingStrArray(it1, it2);
    //System.out.println("Path:"+result);
    //result.setLInfoTree(it1);
    //result.setRInfoTree(it2);
    return result;
  }

  /**
   * Initialization method.
   * 
   * @param t1 first tree to compare.
   * @param t2 second tree to compare.
   */
  private void init(final LblTree t1, final LblTree t2)
  {
    ld = new LabelDictionary();
    it1 = new InfoTree(t1, ld);
    it2 = new InfoTree(t2, ld);
    IJ = new int[Math.max(it1.getSize(), it2.getSize())][Math.max(
        it1.getSize(), it2.getSize())];
    delta = new EditPath[it1.getSize()][it2.getSize()];
    deltaBit = new int[it1.getSize()][it2.getSize()];
    //costV = new long[3][it1.getSize()][it2.getSize()];
    costV = new EnumMap<NodeType,long[][]>(NodeType.class);
    costW = new EnumMap<NodeType,long[]>(NodeType.class);

    final LblTree[] post2nodes1 = it1.getPost2nodes();
    final LblTree[] post2nodes2 = it2.getPost2nodes();
    final int[] postSizes1 = it1.getInfo(PathType.POST2_SIZE);
    final int[] postSizes2 = it2.getInfo(PathType.POST2_SIZE);
    for (int x = 0; x < postSizes1.length; x++) {
      for (int y = 0; y < postSizes2.length; y++) {
        deltaBit[x][y] = 0;
        if (post2nodes1[x].getType() != post2nodes2[y].getType()) {
          deltaBit[x][y] += costFullMatch;
        }
        else if (post2nodes1[x].getLabel() != post2nodes2[y].getLabel()) {
          deltaBit[x][y] += costPartialMatch;
        }
        //System.out.println(" Delta Bit["+x+"]["+y+"]"+deltaBit[x][y] );
      }
    }
  }
  /**
   * A method for computing and storing the optimal strategy.
   */
  private void computeOptimalStrategy()
  {
    StratType strategy = StratType.NONE;
    int parent1 = -1;
    int parent2 = -1;
    final int[] post2size1 = it1.getInfo(PathType.POST2_SIZE);
    final int[] post2size2 = it2.getInfo(PathType.POST2_SIZE);
    final EnumMap<StratType, Long> mins = new EnumMap<StratType, Long>(
        StratType.class);
    mins.put(StratType.NONE,Long.MAX_VALUE);
    mins.put(StratType.BOTH,Long.MAX_VALUE);

    strategyArray = new StratType[it1.getSize()][it2.getSize()];

    // v represents nodes of left input tree in postorder
    // w represents nodes of right input tree in postorder
    costW.put(NodeType.LEFT,new long[it2.getSize()]);
    costW.put(NodeType.RIGHT,new long[it2.getSize()]);
    costW.put(NodeType.HEAVY,new long[it2.getSize()]);
    costV.put(NodeType.LEFT,new  long[it1.getSize()][it2.getSize()]);
    costV.put(NodeType.RIGHT,new long[it1.getSize()][it2.getSize()]);
    costV.put(NodeType.HEAVY,new long[it1.getSize()][it2.getSize()]);
    for (int v = 0; v < it1.getSize(); v++) {
      Arrays.fill(costW.get(NodeType.LEFT), 0);
      Arrays.fill(costW.get(NodeType.RIGHT), 0);
      Arrays.fill(costW.get(NodeType.HEAVY), 0);
      for (int w = 0; w < it2.getSize(); w++) {
        if (post2size2[w] == 1) {
          /* put zeros into arraysi */
          costW.get(NodeType.LEFT)[w] = 0;
          costW.get(NodeType.RIGHT)[w] = 0;
          costW.get(NodeType.HEAVY)[w] = 0;
        }
        if (post2size1[v] == 1) {
          // put zeros into arrays
          costV.get(NodeType.LEFT)[v][w] = 0;
          costV.get(NodeType.RIGHT)[v][w] = 0;
          costV.get(NodeType.HEAVY)[v][w] = 0;
        }

        // count the minimum + get the strategy
        long min = (long) post2size1[v] * (long) it2.getInfo(PathType.POST2_DESC_SUM)[w]
            + costV.get(NodeType.HEAVY)[v][w];
        mins.put(StratType.HEAVY,min);
        min = (long) post2size2[w] * (long) it1.getInfo(PathType.POST2_DESC_SUM)[v]
            + costW.get(NodeType.HEAVY)[w];
        mins.put(StratType.REVHEAVY,min);

        min = (long) post2size1[v] * (long) it2.getInfo(PathType.POST2_KR_SUM)[w]
            + costV.get(NodeType.LEFT)[v][w];
        mins.put(StratType.LEFT,min);
        min = (long) post2size2[w] * (long) it1.getInfo(PathType.POST2_KR_SUM)[v]
            + costW.get(NodeType.LEFT)[w];
        mins.put(StratType.REVLEFT,min);

        min = (long) post2size1[v] * (long)it2.getInfo(PathType.POST2_REV_KR_SUM)[w]
            + costV.get(NodeType.RIGHT)[v][w];
        mins.put(StratType.RIGHT,min);
        min = (long) post2size2[w] * (long) it1.getInfo(PathType.POST2_REV_KR_SUM)[v]
            + costW.get(NodeType.RIGHT)[w];
        mins.put(StratType.REVRIGHT,min);

        min = Long.MAX_VALUE;
        for (StratType str : StratType.values() ){
          if (mins.get(str) <= min) {
            min = mins.get(str);
            strategy = str;
          }
        }

        // store the strategy for the minimal cost
        strategyArray[v][w] = strategy;

        // fill the cost arrays
        parent1 =it1.getInfo(PathType.POST2_PARENT)[v];
        if (parent1 != -1) {
          if (it1.getNodeType(NodeType.HEAVY)[v]){
            costV.get(NodeType.HEAVY)[parent1][w] += costV.get(NodeType.HEAVY)[v][w];
          }
          else {
            costV.get(NodeType.HEAVY)[parent1][w] += min;
          }
          if (it1.getNodeType(NodeType.RIGHT)[v]){
            costV.get(NodeType.RIGHT)[parent1][w] += costV.get(NodeType.RIGHT)[v][w];
          }
          else{
            costV.get(NodeType.RIGHT)[parent1][w] += min;
          }
          if (it1.getNodeType(NodeType.LEFT)[v]){
            costV.get(NodeType.LEFT)[parent1][w] += costV.get(NodeType.LEFT)[v][w];
          }
          else{
            costV.get(NodeType.LEFT)[parent1][w] += min;
          }
        }
        parent2 =it2.getInfo(PathType.POST2_PARENT)[w];
        if (parent2 != -1) {
          if (it2.getNodeType(NodeType.HEAVY)[w] ){
            costW.get(NodeType.HEAVY)[parent2] += costW.get(NodeType.HEAVY)[w];
          }
          else {
            costW.get(NodeType.HEAVY)[parent2] += min;
          }
          if (it2.getNodeType(NodeType.LEFT)[w]){
            costW.get(NodeType.LEFT)[parent2] += costW.get(NodeType.LEFT)[w];
          }
          else{
            costW.get(NodeType.LEFT)[parent2] += min;
          }
          if ( it2.getNodeType(NodeType.RIGHT)[w]){
            costW.get(NodeType.RIGHT)[parent2] += costW.get(NodeType.RIGHT)[w];
          }
          else{
            costW.get(NodeType.RIGHT)[parent2] += min;
          }
        }
      }
    }
  }

  private EditPath computeDistUsingStrArray(InfoTree it1, InfoTree it2)
  {
    // currentNode starts with size-1
    EditPath result;
    int postorder1 = it1.getCurrentNode();
    int postorder2 = it2.getCurrentNode();
    //System.out.println("ComputeUA currNode1:"+postorder1+" cN2:"+postorder2);

    StratType stepStrategy = strategyArray[postorder1][postorder2];

    int tmpPostorder;

    int[] stepPath;
    int[] stepRelSubtrees;
    //ArrayList<Integer> heavyPath;
    //stepStrategy = StratType.LEFT;
    switch (stepStrategy) {
      case LEFT:
        tmpPostorder = postorder1;
        stepPath = it1.getPath(NodeType.LEFT);
        // go along the path
        while (stepPath[postorder1] > -1) {
          stepRelSubtrees = it1.getNodeRelSubtrees(NodeType.LEFT, postorder1);
          if (stepRelSubtrees != null) {
            // iterate over rel subtrees for a specific node on the path
            for (int rs : stepRelSubtrees) {
              it1.setCurrentNode(rs);
              // make the recursion
              computeDistUsingStrArray(it1, it2);
            }
          }
          postorder1 = stepPath[postorder1];
        }
        // set current node
        it1.setCurrentNode(tmpPostorder);
        it1.setSwitched(false);
        it2.setSwitched(false);
        // count the distance using a single-path function
        //strStat[3]++;
        //strStat[InfoTree.LEFT]++;
        result = spfL(it1, it2);
        //System.out.println("spfL x:"+it1.getCurrentNode()+" y:"+it2.getCurrentNode()+ " path:"+result);
        return result;
      case RIGHT:
      case HEAVY:
        tmpPostorder = postorder1;
        stepPath = it1.getPath(NodeType.RIGHT);
        while (stepPath[postorder1] > -1) {
          stepRelSubtrees = it1.getNodeRelSubtrees(NodeType.RIGHT, postorder1);
          if (stepRelSubtrees != null) {
            for (int rs : stepRelSubtrees) {
              it1.setCurrentNode(rs);
              computeDistUsingStrArray(it1, it2);
            }
          }
          postorder1 = stepPath[postorder1];
        }
        it1.setCurrentNode(tmpPostorder);
        it1.setSwitched(false);
        it2.setSwitched(false);
        //strStat[3]++;
        //strStat[InfoTree.RIGHT]++;
        result = spfR(it1, it2).sort();
        //System.out.println("spfR cN:"+tmpPostorder+ " path:"+result);
        return result;
        //tmpPostorder = postorder1;
        //stepPath = it1.getPath(NodeType.HEAVY);
        //heavyPath = new ArrayList<Integer>();
        //heavyPath.add(postorder1);
        //while (stepPath[postorder1] > -1) {
          //stepRelSubtrees = it1.getNodeRelSubtrees(NodeType.HEAVY, postorder1);
          //if (stepRelSubtrees != null) {
            //for (int rs : stepRelSubtrees) {
              //it1.setCurrentNode(rs);
              //computeDistUsingStrArray(it1, it2);
            //}
          //}
          //postorder1 = stepPath[postorder1];
          //heavyPath.add(postorder1);
        //}
        //it1.setCurrentNode(tmpPostorder);
        //it1.setSwitched(false);
        //it2.setSwitched(false);
        ////strStat[3]++;
        ////strStat[InfoTree.HEAVY]++;
        //return spfH(it1, it2, InfoTree.toIntArray(heavyPath));
      case REVLEFT:
        tmpPostorder = postorder2;
        stepPath = it2.getPath(NodeType.LEFT);
        while (stepPath[postorder2] > -1) {
          stepRelSubtrees = it2.getNodeRelSubtrees(NodeType.LEFT, postorder2);
          if (stepRelSubtrees != null) {
            for (int rs : stepRelSubtrees) {
              it2.setCurrentNode(rs);
              computeDistUsingStrArray(it1, it2);
            }
          }
          postorder2 = stepPath[postorder2];
        }
        it2.setCurrentNode(tmpPostorder);
        it1.setSwitched(true);
        it2.setSwitched(true);
        //strStat[3]++;
        //strStat[InfoTree.LEFT]++;
        result = spfL(it2, it1).sort();
        //System.out.println("RspfL cN:"+tmpPostorder+ " path:"+result);
        return result;
      case REVRIGHT:
      case REVHEAVY:
        tmpPostorder = postorder2;
        stepPath = it2.getPath(NodeType.RIGHT);
        while (stepPath[postorder2] > -1) {
          stepRelSubtrees = it2.getNodeRelSubtrees(NodeType.RIGHT, postorder2);
          if (stepRelSubtrees != null) {
            for (int rs : stepRelSubtrees) {
              it2.setCurrentNode(rs);
              computeDistUsingStrArray(it1, it2);
            }
          }
          postorder2 = stepPath[postorder2];
        }
        it2.setCurrentNode(tmpPostorder);
        it1.setSwitched(true);
        it2.setSwitched(true);
        //strStat[3]++;
        //strStat[StratType.RIGHT]++;
        result = spfR(it2, it1).sort();
        //System.out.println("RspfR cN:"+tmpPostorder+ " path:"+result);
        return result;
        //tmpPostorder = postorder2;
        //stepPath = it2.getPath(NodeType.HEAVY);
        //heavyPath = new ArrayList<Integer>();
        //heavyPath.add(postorder2);
        //while (stepPath[postorder2] > -1) {
          //stepRelSubtrees = it2.getNodeRelSubtrees(NodeType.HEAVY, postorder2);
          //if (stepRelSubtrees != null) {
            //for (int rs : stepRelSubtrees) {
              //it2.setCurrentNode(rs);
              //computeDistUsingStrArray(it1, it2);
            //}
          //}
          //postorder2 = stepPath[postorder2];
          //heavyPath.add(postorder2);
        //}
        //it2.setCurrentNode(tmpPostorder);
        //it1.setSwitched(true);
        //it2.setSwitched(true);
        ////strStat[3]++;
        ////strStat[StratType.HEAVY]++;
        //return spfH(it2, it1, InfoTree.toIntArray(heavyPath));
      case NONE:
      default:
        return emptyPath();
    }
  }
  /**
   * Single-path function for the left-most path based on Zhang and Shasha
   * algorithm.
   * 
   * @param it1
   * @param it2
   * @return distance between subtrees it1 and it2
   */
  private EditPath spfL(InfoTree it1, InfoTree it2)
  {
    int fPostorder = it1.getCurrentNode();
    int gPostorder = it2.getCurrentNode();

    int minKR = it2.getInfo(PathType.POST2_MIN_KR)[gPostorder];
    int[] kr = it2.getInfo(PathType.KR);
    if (minKR > -1) {
      for (int j = minKR; kr[j] < gPostorder; j++) {
        treeEditDist(it1, it2, fPostorder, kr[j],true);
      }
    }
    treeEditDist(it1, it2, fPostorder, gPostorder,true);
    if(it1.isSwitched()){
      //if (deltaBit[gPostorder][fPostorder]){
        //EditPath result =delta[gPostorder][fPostorder].copy();
        //result.addMatch(gPostorder,fPostorder);
        //return result;
      //}
      return delta[gPostorder][fPostorder];
    }
    else{
      //if (deltaBit[fPostorder][gPostorder]){
        //EditPath result =delta[fPostorder][gPostorder].copy();
        //result.addMatch(fPostorder,gPostorder);
        //return result;
      //}
      return delta[fPostorder][gPostorder]; 
    }
  }

  /**
   * Calculate tree edit distance for the forests
   * 
   * @param it1
   * @param it2
   * @param i
   * @param j
   * @param leftStrat
   */
  private void treeEditDist(InfoTree it1, InfoTree it2, int i, int j, boolean leftStrat)
  {
    //System.out.println(" Tree Edit i="+i+" j="+j+"********************************************");
    //m, n - size of subforest + 1 for empty
    final int m = i - it1.getInfo(PathType.POST2_LLD)[i] + 2;
    final int n = j - it2.getInfo(PathType.POST2_LLD)[j] + 2;
    final EditPath[][] forestdist = new EditPath[m][n];
    final int ioff = it1.getInfo(PathType.POST2_LLD)[i] - 1;
    final int joff = it2.getInfo(PathType.POST2_LLD)[j] - 1;
    final boolean switched = it1.isSwitched();
    forestdist[0][0] = emptyPath();
    if(switched){
      for (int i1 = 1; i1 < m; i1++) {
        forestdist[i1][0] = forestdist[i1 - 1][0].copy();
        forestdist[i1][0].rmRightNode(joff+1,i1+ioff,leftStrat); //
      }
      for (int j1 = 1; j1 < n; j1++) {
        forestdist[0][j1] = forestdist[0][j1 - 1].copy();
        forestdist[0][j1].insRightNode(j1+joff,ioff+1,leftStrat);
      }
    }
    else{
      for (int i1 = 1; i1 < m; i1++) {
        forestdist[i1][0] = forestdist[i1 - 1][0].copy();
        forestdist[i1][0].insRightNode(i1+ioff,joff+1,leftStrat); //
      }
      for (int j1 = 1; j1 < n; j1++) {
        forestdist[0][j1] = forestdist[0][j1 - 1].copy();
        forestdist[0][j1].rmRightNode(ioff+1,j1+joff,leftStrat);
      }
    }
    for (int i1 = 1; i1 < m; i1++) {
      for (int j1 = 1; j1 < n; j1++) {
        //single tree case
        if(switched){
          da = forestdist[i1 - 1][j1].copy();
          da.rmRightNode(j1+joff,i1+ioff,leftStrat); //
          db = forestdist[i1][j1 - 1].copy();
          db.insRightNode(j1+joff,i1+ioff,leftStrat);
        }
        else{
          da = forestdist[i1 - 1][j1].copy();
          da.insRightNode(i1+ioff,j1+joff,leftStrat);
          db = forestdist[i1][j1 - 1].copy();
          db.rmRightNode(i1+ioff,j1+joff,leftStrat); //costIns
        }
        if(da.getCost()<db.getCost()){
          //db will contain smaller of the two edit distances
          db = da;
        }
        //System.out.println("    F db:"+db);
        if ((it1.getInfo(PathType.POST2_LLD)[i1 + ioff] == 
              it1.getInfo(PathType.POST2_LLD)[i])
            && (it2.getInfo(PathType.POST2_LLD)[j1 + joff] == 
              it2.getInfo(PathType.POST2_LLD)[j])) {
          dc = matchPath(i1+ioff,j1+joff,switched);
          dc.add(forestdist[i1 - 1][j1 - 1]);
          //System.out.println("    FT dc:"+dc);

          if(db.getCost()<=dc.getCost()){
            //take the minimum of three and store in dc.
            dc = db;
          }
          forestdist[i1][j1] = dc;
          //System.out.println("  FT chosen ij=["+(i1+ioff)+" "+(j1+joff)+"] dc:"+dc+"################");

          setDelta(i1 + ioff, j1 + joff, forestdist[i1][j1],
              switched);
        }
        //many subforests case
        else {
          dc = getDelta(i1+ioff,j1+joff,switched);
          dc.add(forestdist[it1.getInfo(PathType.POST2_LLD)[i1 + ioff] - 1 - ioff][it2.getInfo(PathType.POST2_LLD)[j1
              + joff] - 1 - joff]);
          //System.out.println("  FF i="+(it1.getInfo(PathType.POST2_LLD)[i1 + ioff] - 1) +" j="+(it2.getInfo(PathType.POST2_LLD)[j1
              //+ joff] - 1)+" dc:"+dc);
          if(db.getCost()<=dc.getCost()){
            //take the minimum of three and store in dc.
            dc = db;
          }
          forestdist[i1][j1] = dc;
          //System.out.println("  FF chosen ij=["+(i1+ioff)+" "+(j1+joff)+"] dc:"+dc+"----------");
        }
      }
    }
  }

  /**
   * Single-path function for right-most path based on symmetric version of
   * Zhang and Shasha algorithm.
   * 
   * @param it1
   * @param it2
   * @return distance between subtrees it1 and it2
   */
  private EditPath spfR(InfoTree it1, InfoTree it2)
  {

    int fReversedPostorder = it1.getSize() - 1
        - it1.getInfo(PathType.POST2_PRE)[it1.getCurrentNode()];
    int gReversedPostorder = it2.getSize() - 1
        - it2.getInfo(PathType.POST2_PRE)[it2.getCurrentNode()];
    //if(it1.getCurrentNode()==2){
      //System.out.println("fRP:"+fReversedPostorder);
      //System.out.println("gRP:"+gReversedPostorder);
    //}
    int minRKR = it2.getInfo(PathType.RPOST2_MIN_RKR)[gReversedPostorder];
    int[] rkr = it2.getInfo(PathType.RKR);
    if (minRKR > -1) {
      for (int j = minRKR; rkr[j] < gReversedPostorder; j++) {
        treeEditDistRev(it1, it2, fReversedPostorder, rkr[j],false);
      }
    }
    treeEditDistRev(it1, it2, fReversedPostorder, gReversedPostorder,false);
    if(it1.isSwitched()){
      //if(deltaBit [it2.getCurrentNode()] [it1.getCurrentNode()] ){
        //EditPath result =delta[it2.getCurrentNode()][it1.getCurrentNode()].copy();
        //result.addMatch(it2.getCurrentNode(),it1.getCurrentNode());
        //return result;
      //}
      return delta[it2.getCurrentNode()][it1.getCurrentNode()];

    }
    else{
      //if(deltaBit[it1.getCurrentNode()][it2.getCurrentNode()]){
        //EditPath result =delta[it1.getCurrentNode()][it2.getCurrentNode()].copy();
        //result.addMatch(it1.getCurrentNode(),it2.getCurrentNode());
        //return result;
      //}
      return  delta[it1.getCurrentNode()][it2.getCurrentNode()];
    }
  }


  private void treeEditDistRev(InfoTree it1, InfoTree it2, int i, int j,boolean leftStrat)
  {
    final int m = i - it1.getInfo(PathType.RPOST2_RLD)[i] + 2;
    final int n = j - it2.getInfo(PathType.RPOST2_RLD)[j] + 2;
    final EditPath[][] forestdist = new EditPath[m][n];
    final int ioff = it1.getInfo(PathType.RPOST2_RLD)[i] - 1;
    final int joff = it2.getInfo(PathType.RPOST2_RLD)[j] - 1;
    final boolean switched = it1.isSwitched();
    forestdist[0][0] = emptyPath();;
    if(switched){
      for (int i1 = 1; i1 < m; i1++) {
        forestdist[i1][0] = forestdist[i1 - 1][0].copy();
        forestdist[i1][0].rmRightNode(joff+1,i1+ioff,leftStrat); //
      }
      for (int j1 = 1; j1 < n; j1++) {
        forestdist[0][j1] = forestdist[0][j1 - 1].copy();
        forestdist[0][j1].insRightNode(j1+joff,ioff+1,leftStrat);
      }
    }
    else{
      for (int i1 = 1; i1 < m; i1++) {
        forestdist[i1][0] = forestdist[i1 - 1][0].copy();
        forestdist[i1][0].insRightNode(i1+ioff,joff+1,leftStrat); //
      }
      for (int j1 = 1; j1 < n; j1++) {
        forestdist[0][j1] = forestdist[0][j1 - 1].copy();
        forestdist[0][j1].rmRightNode(ioff+1,j1+joff,leftStrat);
      }
    }
    for (int i1 = 1; i1 <= i - ioff; i1++) {
      for (int j1 = 1; j1 <= j - joff; j1++) {
        int iRLD = it1.getInfo(PathType.RPOST2_RLD)[i1 + ioff];
        int iPost = it1.getInfo(PathType.RPOST2_POST)[i1 + ioff];
        int jRLD = it2.getInfo(PathType.RPOST2_RLD)[j1 + joff];
        int jPost = it2.getInfo(PathType.RPOST2_POST)[j1 + joff];
        da = forestdist[i1 - 1][j1].copy();
        db = forestdist[i1][j1 - 1].copy();
        if(switched){
          da.rmRightNode(jPost,iPost,leftStrat); //
          db.insRightNode(jPost,iPost,leftStrat);
        }
        else{
          da.insRightNode(iPost,jPost,leftStrat);
          db.rmRightNode(iPost,jPost,leftStrat); //costIns
        }
        if(da.getCost()<db.getCost()){
          //db will contain smaller of the two edit distances
          db = da;
        }
        //counter++;
        if ((iRLD == it1.getInfo(PathType.RPOST2_RLD)[i])
            && (jRLD == it2.getInfo(PathType.RPOST2_RLD)[j])) {
          dc = matchPath(iPost,jPost,switched);
          dc.add(forestdist[i1 - 1][j1 - 1]);
          if(db.getCost()<=dc.getCost()){
            //take the minimum of three and store in dc.
            dc = db;
          }
          forestdist[i1][j1] = dc;
          setDelta(iPost, jPost, forestdist[i1][j1], switched);
        }
        else {
          dc = getDelta(iPost,jPost,switched);
          dc.add(forestdist[iRLD - 1 - ioff][jRLD - 1 - joff]);
          if(db.getCost()<=dc.getCost()){
            //take the minimum of three and store in dc.
            dc = db;
          }
          forestdist[i1][j1] = dc;
        }
      }
    }
  }


  /**
   * Single-path function for heavy path based on Klein/Demaine algorithm.
   * 
   * @param it1
   * @param it2
   * @param heavyPath
   * @return distance between subtrees it1 and it2
   */
  //private EditPath spfH(InfoTree it1, InfoTree it2, int[] heavyPath)
  //{
  /**
   * T array from Demaine's algorithm, stores delta(Fv,Gij), v on heavy path.
   */
    //EditPath[][] t;

    //int gSize = it2.getInfo(PathType.POST2_SIZE)[it2.getCurrentNode()];

    //int gRevPre = it2.getSize() - 1 - it2.getCurrentNode();
    //int gPre = it2.getInfo(PathType.POST2_PRE)[it2.getCurrentNode()];

    //StratType strategy;

    //int jOfi;

    //t = new EditPath[gSize][gSize];


    //int vp = -1;
    //int nextVp = -1;

    //for (int it = heavyPath.length - 1; it >= 0; it--) {
      //vp = heavyPath[it];
      //strategy = it1.getPostStrategy()[vp];
      //if (strategy != StratType.BOTH) {
        //if (it1.getInfo(PathType.POST2_SIZE)[vp] == 1) {
          //for (int i = gSize - 1; i >= 0; i--) {
            //jOfi = jOfI(it2, i, gSize, gRevPre, gPre, strategy);
            //for (int j = jOfi; j >= 0; j--) {
              //t[i][j] = (gSize - (i + j)) * costMatch;
            //}
          //}
          //previousStrategy = strategy;
        //}
        //computePeriod(it1, vp, nextVp, it2, strategy,t.clone(),t);
      //}
      //else {
        //if (it1.getInfo(PathType.POST2_SIZE)[vp] == 1) {
          //for (int i = gSize - 1; i >= 0; i--) {
            //jOfi = jOfI(it2, i, gSize, gRevPre, gPre, StratType.LEFT);
            //for (int j = jOfi; j >= 0; j--) {
              //t[i][j] = (gSize - (i + j)) * costMatch;
            //}
          //}
          //previousStrategy = StratType.LEFT;
        //}
        //computePeriod(it1, vp, nextVp, it2, StratType.LEFT,t.clone(),t);
        //if (it1.getInfo(PathType.POST2_SIZE)[vp] == 1) {
          //for (int i = gSize - 1; i >= 0; i--) {
            //jOfi = jOfI(it2, i, gSize, gRevPre, gPre, StratType.RIGHT);
            //for (int j = jOfi; j >= 0; j--) {
              //t[i][j] = (gSize - (i + j)) * costMatch;
            //}
          //}
          //previousStrategy = StratType.RIGHT;
        //}
        //computePeriod(it1, vp, nextVp, it2, StratType.RIGHT,t.clone(),t);
      //}
      //nextVp = vp;
    //}
    //return t[0][0];
  //}

  /**
   * Compute period method.
   * 
   * @param it1
   * @param aVp
   * @param aNextVp
   * @param it2
   * @param aStrategy
   */
  /*
  private void computePeriod(final InfoTree it1, final int aVp,
      final int aNextVp, final InfoTree it2, final StratType aStrategy,final EditPath[][] tTable_copy, final EditPath[][] t)
  {

    final int vpPreorder = it1.getInfo(PathType.POST2_PRE)[aVp];
    final int vpRevPreorder = it1.getSize() - 1 - aVp;
    final int vpSize = it1.getInfo(PathType.POST2_SIZE)[aVp];

    final int gSize = it2.getInfo(PathType.POST2_SIZE)[it2.getCurrentNode()];
    final int gPreorder = it2.getInfo(PathType.POST2_PRE)[it2.getCurrentNode()];
    final int gRevPreorder = it2.getSize() - 1 - it2.getCurrentNode();

    int nextVpPreorder = -1;
    int nextVpRevPreorder = -1;
    int nextVpSize = -1;
    // count k and assign next vp values
    int k;
    if (aNextVp != -1) {
      nextVpPreorder = it1.getInfo(PathType.POST2_PRE)[aNextVp];
      nextVpRevPreorder = it1.getSize() - 1 - aNextVp;
      nextVpSize = it1.getInfo(PathType.POST2_SIZE)[aNextVp];
      // if strategy==LEFT use preorder to count number of left deletions from
      // vp to vp-1
      // if strategy==RIGHT use reversed preorder
      if(aStrategy == StratType.LEFT ){
        k = nextVpPreorder - vpPreorder;
      }
      else{
        k = nextVpRevPreorder - vpRevPreorder;
      }
      if (aStrategy != previousStrategy) {
        computeIJTable(it2, gPreorder, gRevPreorder, gSize, aStrategy);
      }
    }
    else {
      k = 1;
      computeIJTable(it2, gPreorder, gRevPreorder, gSize, aStrategy);
    }

    StratType realStrategy = it1.getPostStrategy()[aVp];

    boolean switched = it1.isSwitched();

    // Q and T are visible for every i
    final EditPath[] qTable = new EditPath[k];

    // if aVp is a leaf => precompute table T - edit distance betwen EMPTY and
    // all subforests of G

    // check if nextVp is the only child of vp
    if (vpSize - nextVpSize == 1) {
      // update delta from T table => dist between Fvp-1 and G was computed in
      // previous compute period
      if (gSize == 1) {
        int tX = it1.getInfo(PathType.PRE2_POST)[vpPreorder]; 
        int tY = it2.getInfo(PathType.PRE2_POST)[gPreorder];
        delta[tX][tY]= emptyPath();
        delta[tX][tY].rmAllChildren(tX,!switched);
        //setDeltaValue(it1.getInfo(PathType.PRE2_POST)[vpPreorder], 
            //it2.getInfo(PathType.PRE2_POST)[gPreorder], vpSize - 1, switched);
      }
      else {
        setDeltaValue(it1.getInfo(PathType.PRE2_POST)[vpPreorder],
            it2.getInfo(PathType.PRE2_POST)[gPreorder], t[1][0], switched);
      }
    }

    EditPath[][] sTable;// = new double[k][gTreeSize+1];

    int gijForestPreorder;
    int previousI;
    int jPrime;
    int kBis;
    int jOfIminus1;
    int gijOfIMinus1Preorder;
    int jOfI;
    EditPath deleteFromLeft;
    EditPath deleteFromRight;
    EditPath match;
    int fLabel;
    int gLabel;

    // Q and T are visible for every i
    for (int i = gSize - 1; i >= 0; i--) {

      // jOfI was already computed once in spfH
      jOfI = jOfI(it2, i, gSize, gRevPreorder, gPreorder, aStrategy);

      // when strategy==BOTH first LEFT then RIGHT is done

      //counter += realStrategy == StratType.BOTH && aStrategy == StratType.LEFT ? (k - 1)
          //* (jOfI + 1) : k * (jOfI + 1);

      // compute table S - visible for actual i
     
      sTable = new EditPath[k][jOfI + 1]; 
      // initialized outside loop? -> doesn't work

      for (int kPrime = 1; kPrime <= k; kPrime++) {

        final int fForestPreorderKPrime = aStrategy == StratType.LEFT ? vpPreorder + (k - kPrime)
            : it1.getInfo(PathType.POST2_PRE)[it1.getSize() - 1
                - (vpRevPreorder + (k - kPrime))];
        kBis = kPrime
            - it1.getInfo(PathType.POST2_SIZE)[it1.getInfo(PathType.PRE2_POST)[fForestPreorderKPrime]];

        // reset the minimum arguments' values
        deleteFromRight = costDel;//costIns
        deleteFromLeft = costDel;
        match = emptyPath();
        if (aStrategy == StratType.LEFT){
          match += kBis + nextVpSize;
        }
        else{
          match += vpSize - k + kBis;
        }

        if ((i + jOfI) == (gSize - 1)) {
          deleteFromRight += (vpSize - (k - kPrime));
        }
        else {
          deleteFromRight += qTable[kPrime - 1];
        }

        fLabel = it1.getInfo(PathType.POST2_LABEL)[it1.getInfo(PathType.PRE2_POST)[fForestPreorderKPrime]];

        for (int j = jOfI; j >= 0; j--) {
          // count dist(FkPrime, Gij) with min

          // delete from left
          if(aStrategy == StratType.LEFT){
            gijForestPreorder = IJ[i][j];
          }
          else{
            gijForestPreorder = it2.getInfo(PathType.POST2_PRE)[it2.getSize() - 1 - IJ[i][j]];
          }

          if (kPrime == 1) {
            // if the direction changed from the previous period to this one use
            // i and j of previous strategy

            // since T is overwritten continously, thus use T_copy for getting
            // values from previous period

            if (aStrategy != previousStrategy) {
              if (aStrategy == StratType.LEFT) {
                previousI = gijForestPreorder - gPreorder; // minus preorder of
                                                           // G
              }
              else {
                previousI = it2.getSize() - 1
                    - it2.getInfo(PathType.RPOST2_POST)[it2.getSize() - 1 - gijForestPreorder]
                    - gRevPreorder; // minus rev preorder of G
              }
              deleteFromLeft.add(tTable_copy[previousI][i + j - previousI]);
            }
            else {
              deleteFromLeft.add(tTable_copy[i][j]);
            }

          }
          else {
            deleteFromLeft.add(sTable[kPrime - 1 - 1][j]);
          }

          // match
          match += switched ? 
              delta[it2.getInfo(PathType.PRE2_POST)[gijForestPreorder]]
              [it1.getInfo(PathType.PRE2_POST)[fForestPreorderKPrime]] 
              : 
              delta[it1.getInfo(PathType.PRE2_POST)[fForestPreorderKPrime]]
              [it2.getInfo(PathType.PRE2_POST)[gijForestPreorder]];

          jPrime = j + it2.getInfo(PathType.POST2_SIZE)[it2.getInfo(PathType.PRE2_POST)[gijForestPreorder]];

          // if root nodes of L/R Fk' and L/R Gij have different labels add the
          // match cost
          gLabel = it2.getInfo(PathType.POST2_LABEL)[it2.getInfo(PathType.PRE2_POST)[gijForestPreorder]];

          if (fLabel != gLabel) {
            match += costMatch;
          }

          // this condition is checked many times but is not satisfied only once
          if (j != jOfI) {
            // delete from right
            deleteFromRight.add(sTable[kPrime - 1][j + 1]);
            if (kBis == 0) {
              if (aStrategy != previousStrategy) {
                previousI = aStrategy == StratType.LEFT ? IJ[i][jPrime] - gPreorder
                    : IJ[i][jPrime] - gRevPreorder;
                match.add(tTable_copy[previousI][i + jPrime - previousI]);
              }
              else {
                match.add(tTable_copy[i][jPrime]);
              }
            }
            else{
              if (kBis > 0) {
                match.add(sTable[kBis - 1][jPrime]);
              }
              else {
                match += gSize - (i + jPrime);
              }
            }
          }

          // fill S table
          if (deleteFromLeft.getCost() < deleteFromRight.getCost()){
            if (deleteFromLeft.getCost() < match.getCost()){
              sTable[kPrime - 1][j] = deleteFromLeft;
            }
            else{
              sTable[kPrime - 1][j] = match;
            }
          }
          else{
            if(deleteFromRight.getCost() < match.getCost()){
              sTable[kPrime - 1][j] = deleteFromRight;
            }
            else{
              sTable[kPrime - 1][j] = match;
            }
          }

          // reset the minimum arguments' values
          deleteFromRight = costDel;
          deleteFromLeft = costDel;
          match = emptyPath();
        }
      }

      // compute table T => add row to T
      if (realStrategy == StratType.BOTH && aStrategy == StratType.LEFT) {
        t[i] = sTable[k - 1 - 1];
      }
      else {
        t[i] = sTable[k - 1];
      }

      if (i > 0) {
        // compute table Q
        jOfIminus1 = jOfI(it2, i - 1, gSize, gRevPreorder, gPreorder, aStrategy);
        if (jOfIminus1 <= jOfI) {
          // copy whole column |
           // qTable.length=k
          for (int x = 0; x < qTable.length; x++) {
            qTable[x] = sTable[x][jOfIminus1];
          }
        }

        // fill table delta
        if (i + jOfIminus1 < gSize) {

          gijOfIMinus1Preorder = aStrategy == StratType.LEFT ? it2.getInfo(PathType.POST2_PRE)[it2.getSize()
              - 1 - (gRevPreorder + (i - 1))]
              : gPreorder + (i - 1);

          // If Fk from Fk-1 differ with a single node,
          // then Fk without the root node is Fk-1 and the distance value has to
          // be taken from previous T table.
          if (k - 1 - 1 < 0) {
            if (aStrategy != previousStrategy) {
              previousI = aStrategy == StratType.LEFT ? IJ[i][jOfIminus1]
                  - gPreorder
                  : IJ[i][jOfIminus1] - gRevPreorder;
              setDeltaValue(it1.getInfo(PathType.PRE2_POST)[vpPreorder],
                  it2.getInfo(PathType.PRE2_POST)[gijOfIMinus1Preorder],
                  tTable_copy[previousI][i + jOfIminus1 - previousI], switched);
            }
            else {
              setDeltaValue(it1.getInfo(PathType.PRE2_POST)[vpPreorder],
                  it2.getInfo(PathType.PRE2_POST)[gijOfIMinus1Preorder],
                  tTable_copy[i][jOfIminus1], switched);
            }
          }
          else {
            setDeltaValue(it1.getInfo(PathType.PRE2_POST)[vpPreorder],
                it2.getInfo(PathType.PRE2_POST)[gijOfIMinus1Preorder],
                sTable[k - 1 - 1][jOfIminus1], switched);
          }
        }
      }

    }
    previousStrategy = aStrategy;
  }
*/
  /**
   * Computes an array where preorder/rev.preorder of a subforest of given
   * subtree is stored and can be accessed for given i and j.
   * 
   * @param it
   * @param subtreePreorder
   * @param subtreeRevPreorder
   * @param subtreeSize
   * @param aStrategy
   */
  private void computeIJTable(final InfoTree it, final int subtreePreorder,
      final int subtreeRevPreorder, final int subtreeSize, final StratType aStrategy)
  {

    int change;

    final int[] post2pre = it.getInfo(PathType.POST2_PRE);
    final int[] rpost2post = it.getInfo(PathType.RPOST2_POST);

    if (aStrategy == StratType.LEFT) {
      for (int x = 0; x < subtreeSize; x++) {
        IJ[0][x] = x + subtreePreorder;
      }
      for (int x = 1; x < subtreeSize; x++) {
        change = post2pre[it.getSize() - 1 - (x - 1 + subtreeRevPreorder)];
        for (int z = 0; z < subtreeSize; z++) {
          if (IJ[x - 1][z] >= change) {
            IJ[x][z] = IJ[x - 1][z] + 1;
          }
          else {
            IJ[x][z] = IJ[x - 1][z];
          }
        }
      }
    }
    else {// if (aStrategy == RIGHT)
      for (int x = 0; x < subtreeSize; x++) {
        IJ[0][x] = x + subtreeRevPreorder;
      }
      for (int x = 1; x < subtreeSize; x++) {
        change = it.getSize() - 1
            - rpost2post[it.getSize() - 1 - (x - 1 + subtreePreorder)];
        for (int z = 0; z < subtreeSize; z++) {
          if (IJ[x - 1][z] >= change) {
            IJ[x][z] = IJ[x - 1][z] + 1;
          }
          else {
            IJ[x][z] = IJ[x - 1][z];
          }
        }
      }
    }
  }


  /**
   * Returns j for given i, result of j(i) form Demaine's algorithm.
   * 
   * @param it
   * @param aI
   * @param aSubtreeWeight
   * @param aSubtreeRevPre
   * @param aSubtreePre
   * @param aStrategy
   * @param treeSize
   * @return j for given i
   */
  private int jOfI(final InfoTree it,final int aI,final int aSubtreeWeight,
      final int aSubtreeRevPre,
      final int aSubtreePre, final StratType aStrategy)
  {
    if (aStrategy == StratType.LEFT){
      return aSubtreeWeight
          - aI
          - it.getInfo(PathType.POST2_SIZE)[it.getSize() - 1
              - (aSubtreeRevPre + aI)];
    }
    else{
      return aSubtreeWeight
          - aI
          - it.getInfo(PathType.POST2_SIZE)[it.getInfo(PathType.RPOST2_POST)[it.getSize()
              - 1 - (aSubtreePre + aI)]];
    }
  }

  private void setDelta(final int a, final int b, final EditPath value,
      final boolean switched)
  {
    if (switched) {
      delta[b][a] = value;
    }
    else {
      delta[a][b] = value;
    }
  }
  private EditPath getDelta(final int a, final int b, final boolean switched)
  {
    if (switched) {
      return delta[b][a].copy(); 
    }
    else {
      return delta[a][b].copy();
    }
  }


  private EditPath emptyPath()
  {
    return new EditPath(costDel,0);
  }

  private EditPath matchPath(final int x, final int y, final boolean switched)
  {
    final EditPath result = emptyPath();
    if (switched){
      result.addMatch(y,x,deltaBit[y][x]);
      return result;
    }
    else{
      result.addMatch(x,y,deltaBit[x][y]);
      return result;
    }
  }

}

